from typing import List


class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:

        def dfs(board, x, y):
            if y == 9:
                x += 1
                y = 0
            if x == 9:
                return True
            if board[x][y] != '.':
                return dfs(board, x, y+1)
            for i in range(9):
                if not row[x][i] and not col[y][i] and not cell[x//3][y//3][i]:
                    board[x][y] = str(1+i)
                    row[x][i] = col[y][i] = cell[x//3][y//3][i] = True
                    if dfs(board, x, y+1):
                        return True
                    board[x][y] = '.'
                    row[x][i] = col[y][i] = cell[x//3][y//3][i] = False

            return False

        row, col = [[False] * 9 for i in range(9)], [[False] * 9 for i in range(9)]
        cell = [[[False] * 9 for i in range(3)] for j in range(3)]

        for i in range(9):
            for j in range(9):
                if board[i][j] != '.':
                    t = int(board[i][j]) - 1
                    row[i][t] = col[j][t] = cell[i//3][j//3][t] = True

        dfs(board, 0, 0)